package com.leetcode.根据数据结构分类.链表;

import com.leetcode.datastructure.ListNode;

/**
 * @author: ZhouBert
 * @date: 2020/11/19
 * @description: https://leetcode-cn.com/problems/reverse-linked-list/
 */
public class A_206_反转链表 {


	/**
	 * 使用迭代来解决了
	 * 有【三个指针】进行【前进】（模拟了两个指针的情况，并不能解决问题，算法还是需要多比划比划）
	 *
	 * @param head
	 * @return
	 */
	public ListNode reverseList1(ListNode head) {
		//!注意边界判断
		if (head == null) {
			return head;
		}

		ListNode point = head;
		ListNode next = head.next;
		ListNode old = null;
		while (next != null) {
			point.next = old;
			old = point;
			point = next;
			next = next.next;
		}
		point.next = old;
		return point;
	}

	/**
	 * 使用递归进行反转
	 * 递归真的挺异想天开的
	 * 假设有一个方法:
	 * ListNode newNode = reverseListByRecursion(node);
	 * 此时 newNode 已经返回了后面已经反转后的链表，并且 newNode 指向反转后的头节点；
	 * 接下来再去关心反转后的头节点：就是 head
	 *
	 * @param head
	 * @return
	 */
	public static ListNode reverseListByRecursion(ListNode head) {
		if (head == null || head.next == null) {
			return head;
		}
		//newNode 指向反转后的【头节点】
		ListNode newNode = reverseListByRecursion(head.next);
		//将上面递归的参数节点指向自己，即完成了反转
		head.next.next = head;
		head.next = null;
		return newNode;
	}

	public static void main(String[] args) {
		ListNode node1 = new ListNode(1);
		node1.next=new ListNode(2);
		node1.next.next=new ListNode(3);
		reverseListByRecursion(node1);
	}
}
